# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/15 上午10:15
    Author  : Thinkgamer
    File    : 453-最小移动次数使数组元素相等.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/
"""

"""
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。
示例:
输入:
[1,2,3]
输出:
3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

"""

"""
	思路 v1：贪心思想，移动次数最少，那便应该避免最大的值少加1，即每次应该移动最大的值，程序终止条件，即最小值和最大值相等的时候
			提交运行：超时
		v2：因为每次移动的是最大值，所以每移动一次，最小值+1即可，最大值，需要记录其位置和值
			提交运行：超时
		v3：参考评论思路
			n-1个数同时 + 1，相当于 每次有一个数 - 1
			看数据中的所有数 总共需要减多少次能减到和最小值一致
"""


def min_moves_v1(nums):
	def find_max_min_v(nums):
		# 找到第一个最大值，和最小值
		max_v = 0
		min_v = 100000
		max_index = 0
		for i in range(len(nums)):
			if nums[i] > max_v:
				max_v = nums[i]
				max_index = i
			if nums[i] < min_v:
				min_v = nums[i]
		return min_v, max_v, max_index
	
	_len = len(nums)
	# 找到第一个最大值，和最小值
	min_v, max_v, max_index = find_max_min_v(nums)
	count = 0
	while min_v != max_v:
		if max_index != _len - 1:  # 向右侧移动
			temp = nums[max_index + 1]
			nums[max_index + 1] = max_v
			nums[max_index] = temp
			for i in range(_len):
				if i != max_index + 1:
					nums[i] += 1
		else:  # 向左侧移动
			temp = nums[max_index - 1]
			nums[max_index - 1] = max_v
			nums[max_index] = temp
			for i in range(_len):
				if i != max_index - 1:
					nums[i] += 1
		count += 1
		min_v, max_v, max_index = find_max_min_v(nums)
	return count


def min_moves_v2(nums):
	_len = len(nums)
	# 找到第一个最大值，和最小值
	max_v = float("-inf")
	min_v = float("inf")
	max_index = 0
	for i in range(len(nums)):
		if nums[i] > max_v:
			max_v = nums[i]
			max_index = i
		if nums[i] < min_v:
			min_v = nums[i]
	count = 0
	# print("count = {}, min_v = {}, max_v = {}, max_index = {}".format(count, min_v, max_v, max_index))
	while min_v != max_v:
		print(count)
		if max_index != _len - 1:  # 向右侧移动
			# print("右侧移动：{}".format(count))
			temp = nums[max_index + 1]
			nums[max_index + 1] = max_v
			nums[max_index] = temp
			for i in range(_len):
				if i != max_index + 1:
					nums[i] += 1
			# 比较当前最大值和左侧的值
			if nums[max_index] >= max_v:
				max_v = nums[max_index]
				max_index = max_index
			else:
				max_v = nums[max_index + 1]
				max_index += 1
		else:  # 向左侧移动
			# print("左侧移动：{}".format(count))
			temp = nums[max_index - 1]
			nums[max_index - 1] = max_v
			nums[max_index] = temp
			for i in range(_len):
				if i != max_index - 1:
					nums[i] += 1
			# 比较当前最大值和左侧值
			if nums[max_index - 1] >= max_v:
				max_v = nums[max_index-1]
				max_index -= 1
			else:
				max_v = nums[max_index]
				max_index - max_index
		count += 1
		# 每移动一次 最小值 + 1
		min_v += 1
		# print("count = {}, min_v = {}, max_v = {}, max_index = {}".format(count, min_v, max_v, max_index))
	return count


def min_moves_v3(nums):
	min_v = min(nums)
	sum = 0
	for num in nums:
		sum += num - min_v
	return sum


# nums = [1, 2, 3]
# nums = [1, 2147483647]
nums = [-100, 0, 100]
result = min_moves_v3(nums)
print(result)